#include "../tools.h"

// 栈里放索引！！！
class Solution {
public:
    bool checkValidString(string s) {
        stack<int> stleft;
        stack<int> ststar;
        int size = s.size();
        for(int i = 0; i < size; ++i){
            if(s[i] == '(') stleft.push(i);
            else if(s[i] == '*') ststar.push(i);
            else if(s[i] == ')'){
                if(!stleft.empty()){
                    stleft.pop();
                    continue;
                }
                if(!ststar.empty()){
                    ststar.pop();
                    continue;
                }
                return false;
            }
        }

        while(!stleft.empty() && !ststar.empty()){
            int left_index = stleft.top(); stleft.pop();
            int star_index = ststar.top(); ststar.pop();
            if(star_index < left_index) return false;
        }
        if(stleft.empty()) return true;
        return false;

    }
};



int main(int argc, char const *argv[])
{
    Solution sol;

    string str = "(*))";

    cout << sol.checkValidString(str) << endl;

    return 0;
}
